package com.fr.lintcode;

import java.util.ArrayList;

import org.junit.Test;

/**
*作者：furong
*日期：2017年3月27日
*时间：下午3:18:13
*/
public class Q91 {
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
        if (A == null || A.size() <= 1) {
            return 0;
        }
        int length = A.size();
        int max = 0;
        for (int a : A) {
            if (a > max) {
                max = a;
            }
        }
        int dp[][] = new int[length + 1][max + 1];
        for (int i = 1; i <= length; i++) {
            for (int j = 1; j <= max; j++) {
                int minCost = Integer.MAX_VALUE;
                for (int k = 0; k <= target; k++) {
                    if (j > k && dp[i - 1][j - k] < minCost) {
                        minCost = dp[i - 1][j - k];
                    }
                    if (j + k <= max && dp[i - 1][j + k] < minCost) {
                        minCost = dp[i - 1][j + k];
                    }
                }
                dp[i][j] = minCost + Math.abs(j - A.get(i - 1));
            }
        }
        int minCost = Integer.MAX_VALUE;
        for (int j = 1; j <= max; j++) {
            if (dp[length][j] < minCost) {
                minCost = dp[length][j];
            }
        }
        return minCost;
    }

    @Test
    public void testA() {
        // 12,3,7,4,5,13,2,8,4,7,6,5,7 2
        ArrayList<Integer> A = new ArrayList<>();
        A.add(12);
        A.add(3);
        A.add(7);
        A.add(4);
        A.add(5);
        A.add(13);
        A.add(2);
        A.add(8);
        A.add(4);
        A.add(7);
        A.add(6);
        A.add(5);
        A.add(7);
        int target = 2;
        System.out.println(MinAdjustmentCost(A, target));
    }
}
